#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <limits>

using namespace std;

class Fenwick_tree
{
public:
	Fenwick_tree(const vector<int> &arr)
	{
		f.resize(arr.size(), 0);
		for (int i = 0; i < f.size(); ++i)
			update(i, arr[i]);
	}

	int get_sum(int i)
	{
		if (i < 0)
			return 0;
		return f[i] + get_sum(low(i)-1);
	}

	void update(int i, int v)
	{
		while (i < f.size())
		{
			f[i] += v;
			i |= i + 1;
		}
	}

private:
	int low(int i)
	{
		return i & (i + 1);
	}

	vector<int> f;
};

class Parking
{
public:
	Parking(int n_parking_places) : place_status(n_parking_places, FREE),
		ft(Fenwick_tree(vector<int>(n_parking_places,0)))
	{}

	int car_in(int i)
	{
		int first_free = i;
		if (place_status[first_free] == OCCUPIED)
		{
			first_free = search_first_free(i);
		}
		
		if (first_free != -1)
		{
			place_status[first_free] = OCCUPIED;
			ft.update(first_free, 1);
		}

		return first_free;
	}

	int car_out(int i)
	{
		if (place_status[i] == OCCUPIED)
		{
			place_status[i] = FREE;
			ft.update(i, -1);
			return 0;
		}
		return -2;
	}

private:
	enum Place_status
	{
		FREE,
		OCCUPIED
	};

	int binary_search_first_free_rec(int i, int j)
	{
		if (dist(i, j) == 0)
			return i;

		int med = plus(i, dist(i,j)/2),
			num_of_free_slots = 0;

		if (i <= med)
			num_of_free_slots = dist(i, med) - (ft.get_sum(med) - ft.get_sum(i));
		else
			num_of_free_slots = dist(i, med) - (ft.get_sum(med) - (ft.get_sum(place_status.size()-1) - ft.get_sum(i)));

		if (place_status[med] == FREE || num_of_free_slots > 0)
			return binary_search_first_free_rec(i, med);
		else
			return binary_search_first_free_rec(plus(med, 1), j);
	}

	int search_first_free(int i)
	{
		int pos = binary_search_first_free_rec(i, minus(i,1));
		if (place_status[pos] == FREE)
			return pos;
		else
			return -1;
	}

	// i - j
	int minus(int i, int j)
	{
		if (i < j)
			return place_status.size() - abs(i-j);
		else
			return i - j;
	}

	// i + j
	int plus(int i, int j)
	{
		return (i + j) % place_status.size();
	}

	// i is a first index ("leftmost")
	int dist(int i, int j)
	{
		if (j >= i)
			return j - i;
		else
			return (place_status.size() - i) + j;
	}

	vector<Place_status> place_status;
	Fenwick_tree ft;
};

void main()
{
	int n_parking_places;
	cout << "Input the number of parking places: ";
	cin >> n_parking_places;

	int n_cars;
	cout << "Input the number of cars: ";
	cin >> n_cars;

	Parking p(n_parking_places);
	cout << "Input queries:" << endl;
	for (int i_car = 0; i_car < n_cars; ++i_car)
	{
		int cur_query;
		cin >> cur_query;
		if (cur_query >= 0)
			cout << p.car_in(cur_query) << endl;
		else
			cout << p.car_out(-cur_query) << endl;
	}

	cin.ignore(numeric_limits<streamsize>::max(), '\n');
	cin.get();
}